package com.cg.leetcode;

import org.junit.Test;

/**
 * 98. 验证二叉搜索树
 *
 * @program: LeetCode->LeetCode_98
 * @description: 98. 验证二叉搜索树
 * @author: cg
 * @create: 2021-08-20 20:47
 **/
public class LeetCode_98 {

    @Test
    public void test98() {
        //System.out.println(isValidBST(new TreeNode(5, new TreeNode(1), new TreeNode(4, new TreeNode(3), new TreeNode(6)))));
        System.out.println(isValidBST(new TreeNode(2, new TreeNode(1), new TreeNode(3))));
        //System.out.println(isValidBST(new TreeNode(2, new TreeNode(2), new TreeNode(2))));
        //System.out.println(isValidBST(new TreeNode(0, new TreeNode(-1), null)));
    }

    /**
     * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
     * 假设一个二叉搜索树具有如下特征：
     * 1)节点的左子树只包含小于当前节点的数。
     * 2)节点的右子树只包含大于当前节点的数。
     * 3)所有左子树和右子树自身必须也是二叉搜索树。
     * <p>
     * 示例 1:
     * 输入:
     *   2
     *  / \
     * 1   3
     * 输出: true
     * <p>
     * 示例 2:
     * 输入:
     *     5
     *    / \
     *   1   4
     *      / \
     *     3   6
     * 输出: false
     * 解释: 输入为: [5,1,4,null,null,3,6]。
     *      根节点的值为 5 ，但是其右子节点值为 4 。
     *
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        return inorder(root);
    }

    long per = Long.MIN_VALUE;

    private boolean inorder(TreeNode node) {
        if (node == null) {
            return true;
        }
        boolean l = inorder(node.left);
        if (node.val > per) {
            per = node.val;
        } else {
            return false;
        }
        boolean r = inorder(node.right);
        return l && r;
    }

}
